Alan Turing conceived the Turing machine in the 1930's as a basic and fundamental abstract computation device, to be used as an instrument for studying the mathematical concept of computation and computability.
A Turing machine 10, shown in FIG. 1, consists of an infinite storage tape 12 divided into tape cells 14, each cell 14 is capable of storing a single symbol, and a read/write head 16 connecting the tape 12 to a finite control 11. The machine 10 operates according to a control program, consisting of a finite number of state-transition rules, which are quintuples of the form &lt;S,A,S',A',Dir&gt;. Such a rule is interpreted as follows: If the finite control 11 is in state S, and the tape cell 14 of the read/write head 16 contains the symbol A, then change the control state to S', replace the symbol A by A', and move the read/write head 16 one cell 14 in direction Dir (Dir is either "left" or "right"). The Turing machine 10 begins its operation with a finite input written on the otherwise blank tape 12, the read/write head 16 located on the left-most non-blank symbol, and the control in a designated initial state. The computation progresses according to the control program, and terminates when no State-transition rule applies. The content of the non-blank part of tape 12 upon termination is considered the output of the computation.
During the 1930's other mathematical models of computation were developed, including the Lambda Calculus by Alonzo Church and the Primitive Recursive by Kurt Goedel. Following proofs that all these models are equivalent in their computational power, "Church's Thesis" was formulated, stating that all conceivable computational models, past and future, will turn out to be computationally equivalent to each other and in particular to the Turing machine.
While mathematically as powerful as any other computational model, the Turing machine was never implemented as a practical computation device. Turing envisioned his machine being operated by a human being, called "computer" that follows the rules of the control program and uses markers, pencil and an eraser to implement the read/write head 16.
In the 1940's, von Neumann and colleagues conceived the stored-program electronic computer, on which all modern computers are based.
In the 1970's, Charles Bennett performed a theoretical investigation of physical computation devices based on the Turing machine model. Bennett was motivated by the observation that the standard electronic computers are inherently energy-inefficient since their basic "store to memory" operation irreversibly erases the content of the memory location. Bennett believed that due to thermodynamic considerations computation devices that proceed in a reversible way would be more efficient, and he proposed two conceptual implementations of the Turing machine model that are reversible. One of these conceptual implementations, which he called "Brownian computer" since its operation was based on the Brownian motion of molecules, is a precursor to our invention. In Bennett's Brownian computer, named "hypothetical enzymatic Turing machine", the tape is a macromolecule consisting of a structural backbone bearing tape symbols and a head marker, and each quintuple of the control program is realized by a specific enzyme that effects the transition by removing and adding a tape symbol, and moving the location of the head marker. [Reference: Charles, H. Bennett, The Thermodynamics of Computation--A Review, International Journal of Theoretical Physics, Vol. 21, No. 12, 1982, pp.905-940].
More recently, interest in molecular computation devices resumed following the work of Adelman [Leonard M. Adelman, Molecular computation of solutions to combinatorial problems, Science, 266:1021-1024, 1994] in 1994, who showed how DNA segments combined with DNA related enzymes can be used to effect computations. Adelman's method was based on creating a test-tube solution consisting of DNA segments and performing "biological steps", effected by a human or a robot, which include adding certain enzymes to the solution, dividing the solution into several tubes, and/or changing the temperature of the solution. At the end of these steps the result of the computation is extracted via standard biological tools. Following that paper numerous proposals were made on how to implement a DNA-based Turing machine using DNA and related enzymes [Most of this work was reported in the four Proceedings of the Meetings on DNA Based Computers, DIMACS, 1995, 1996, 1997, 1998, and are reviewed in Eric Winfree's Ph.D. Thesis, Algorithmic Self-Assembly of DNA, Caltech, May, 1998]. These proposals fall into two broad classes: one class requires each step of the computation to be effected by a "biological step" as in Adelman's method. The second class [Erik Winfree, Simulations of Computing by Self-Assembly, Preliminary Proceedings of the Fourth International Meeting on DNA Based Computers, DIAMACS, Jun. 15-19, 1998, University of Pennsylvania, edited by Lila Kari, Harvey Rubin and David Harlan Wood, pages 213-239, and references thereto] creates a set of molecules that "self-assemble" in a way that effects a computation. Our invention belongs to that class.